class Solution(object):
  def buildTree(self, preorder, inorder):
    """
    :type preorder: List[int]
    :type inorder: List[int]
    :rtype: TreeNode
    """
    self.preindex = 0
    ind = {v: i for i, v in enumerate(inorder)}
    head = self.dc(0, len(preorder) - 1, preorder, inorder, ind)
    return head

  def dc(self, start, end, preorder, inorder, ind):
    if start <= end:
      mid = ind[preorder[self.preindex]]
      self.preindex += 1
      root = TreeNode(inorder[mid])
      root.left = self.dc(start, mid - 1, preorder, inorder, ind)
      root.right = self.dc(mid + 1, end, preorder, inorder, ind)
      return root
